动态规划

背包问题：有多个重量不同、价值不同的物品，以及一个容量有限的背包，选择一些物品装入背包，求最大总价值。 背包问题无法用贪心求最优解，是典型的动态规划问题。背包问题还可以分成3种：① 0-1背包、② 完全背包、③ 多重背包。

区别

0/1背包

每种物品是一件

完全背包

每种物品是无限件

多重背包

每种物品是有限件

0/1背包顾名思义就是0和1两种状态，即每个物品装入和不装入背包这两种状态，如果不懂dp的话，可能用dfs的做法深搜，但时间复杂度是2n，肯定是不能接受的，或者用贪心，但也并不能得到全局最优解。下面举例说明dp。

假设4个物品，重量分别是w={2,3,6,5}，价值分别是v={6,3,5,4}，背包容量为9。 引进二维表dp[][]，dp[i][j]表示考虑前i个物品装入容量为j的背包中获得的最大价值。可以把每个dp[i][j]都看成一个背包。

步骤一：只装第1个物品 因为物品1的重量是2，所以容量小于2的背包都放不进去（即dp[1][0]=dp[1][1]=0），在容量2时装入，其价值是物品1的价值（即dp[1][2]=6），容量大于2的背包，多余的容量也用不到（因为现在只考虑物品1），其价值也都是6，如下图

0

1

2

3

4

5

6

7

8

9

0

0

0

0

0

0

0

0

0

0

0

1

0

0

6

6

6

6

6

6

6

6

步骤二：只装前2个物品 首先，物品2重量是3，背包容量3的情况和只装物品1情况一样。下面从dp[2][3]开始填，此时我们可以选择装物品2，也可以不装。 如果装，那么相当于把dp[i-1][j-3]的最大价值加上物品2的价值3，即考虑只第一个物品的时候，腾出3容量放物品2，此时价值=3；

如果不装，那么相当于只把物品1装入，此时价值=6；

我们取两者最大值，即dp[2][3]=max(3,6)=6。 后面的多余容量同理。

三.重复上述步骤，得到dp数组

0

1

2

3

4

5

6

7

8

9

0

0

0

0

0

0

0

0

0

0

0

1

0

0

6

6

6

6

6

6

6

6

2

0

0

6

6

6

9

9

9

9

9

3

0

0

6

6

6

9

9

9

11

11

4

0

0

6

6

6

9

9

10

11

11

最后答案是dp[4][9]，即把4个物品装入容量为9的背包，最大价值是11。

现在回过头看装了哪些物品： dp[4][9]=max(dp[3][4]+4，dp[3][9])=dp[3][9]，说明没有装物品4； dp[3][9]=max(dp[2][3]+5，dp[2][9])=dp[2][3]+5,说明装了物品3； 以此类推，如图箭头所示，即装了物品1和3，输出方案即可。

除了这样倒推外，也可以定义数组path[][]，path[i][j]表示状态j下物品i是否被选中，初始化为0，置1表示选中，当更新dp的时候同时维护即可。

HDU-2602 Bone Collector 说了这么多可能有点迷，看下例题和代码可能更易理解。

Problem Description Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave … The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ? Input The first line contain a integer T , the number of cases. Followed by T cases , each case three lines , the first line contain two integer N , V, (N